#ifndef __RBTREE_H
#define __RBTREE_H

struct rb_node {
    unsigned long   __rb_parent_color;
    struct rb_node* rb_right;
    struct rb_node* rb_left;
};

struct rb_root {
    struct rb_node* rb_node;
};

#define rb_entry(ptr, type, member) \
    ((type*)((char*)(ptr) - (unsigned long)(&((type*)0)->member)))

void rb_insert_color(struct rb_node*, struct rb_root*);
void rb_erase(struct rb_node*, struct rb_root*);

/* Find logical next and previous nodes in a tree */
struct rb_node* rb_next(const struct rb_node*);
struct rb_node* rb_prev(const struct rb_node*);
struct rb_node* rb_first(const struct rb_root*);
struct rb_node* rb_last(const struct rb_root*);

/* Postorder iteration - always visit the parent after its children */
struct rb_node* rb_first_postorder(const struct rb_root*);
struct rb_node* rb_next_postorder(const struct rb_node*);

/* Fast replacement of a single node without remove/rebalance/add/rebalance */
void rb_replace_node(
    struct rb_node* victim, struct rb_node* new, struct rb_root* root);

void rb_link_node(
    struct rb_node* node, struct rb_node* parent, struct rb_node** rb_link);

#define rb_entry_safe(ptr, type, member)                  \
    ({                                                    \
        __typeof__(ptr) ____ptr = (ptr);                  \
        ____ptr ? rb_entry(____ptr, type, member) : NULL; \
    })

/**
 * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
 * given type allowing the backing memory of @pos to be invalidated
 *
 * @pos:	the 'type *' to use as a loop cursor.
 * @n:		another 'type *' to use as temporary storage
 * @root:	'rb_root *' of the rbtree.
 * @field:	the name of the rb_node field within 'type'.
 *
 * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
 * list_for_each_entry_safe() and allows the iteration to continue independent
 * of changes to @pos by the body of the loop.
 *
 * Note, however, that it cannot handle other modifications that re-order the
 * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
 * rb_erase() may rebalance the tree, causing us to miss some nodes.
 */
#define rbtree_postorder_for_each_entry_safe(pos, n, root, field)             \
    for(pos =                                                                 \
            rb_entry_safe(rb_first_postorder(root), __typeof__(*pos), field); \
        pos && ({                                                             \
            n = rb_entry_safe(                                                \
                rb_next_postorder(&pos->field), __typeof__(*pos), field);     \
            1;                                                                \
        });                                                                   \
        pos = n)

#endif